We propose a new data structure to compute the Delaunay triangulation of aset of points in the plane. It combines good worst case complexity, fastbehavior on real data, and small memory occupation. The location structure is organized into several levels. The lowest leveljust consists of the triangulation, then each level contains the triangulationof a small sample of the levels below. Point location is done by marching in atriangulation to determine the nearest neighbor of the query at that level,then the march restarts from that neighbor at the level below. Using a smallsample (3%) allows a small memory occupation; the march and the use of thenearest neighbor to change levels quickly locate the query.
展开▼
